Going round in (almost) circles
Introduction
This article describes a very simple and very, very old method of rotating a 2d (x,y) co-ordinate around an origin by a certain angle. This method was used back in the days of 8-bit computers which had NO multiplication or division instructions.
Common 2d-rotation
You should all have this formula etched into your skulls by now.
x' = x * cos(a) - y * sin(a) <--- step 1
y' = x * sin(a) + y * cos(a) <--- step 2
x = x'
y = y'
where,
a = angle to rotate through
(x,y) = old co-ordinate 2d values to rotate
(x',y') = new rotated 2d values
NOTEYou should note the BOTH steps use the old x and y values, and the result is stored in two NEW variables (namely x' and y'). If you try updating (x,y) directly in step 1 then it will fail. You need a minimum of 1 temporary variable.
old_x = x
x = x * cos(a) - y * sin(a)
y = old_x * sin(a) + y * sin(a)
Fast 90-degree rotation
Using the above 2d rotation formula you can replace those nasty cos(a) and sin(a) with constant values for a 90 degree rotation.
cs = cos(90) = 0
sn = sin(90) = 1
x' = (x * cs) - (y * sn)
y' = (x * sn) + (y * cs)
which is,
x' = (x * 0) - (y * 1)
y' = (x * 1) + (y * 0)
which gives:
x' = - (y * 1)
y' = (x * 1)
and is:
x' = - y
y' = x
In Code this can be done in just two instructions which can be very useful when you want to quickly draw a border or to preform some 90 degree rotation.
(eax) = x
(edx) = y
XCHG EAX, EDX
NEG EAX
Of course you could replace cs and sn with some other constants and yield 180 degree or 270 degree rotation using nothing more than XCHG and NEG instructions. If you want to rotate by a non-multiple of 90, then you need to use some multiplication.
Constant Rotation
As you have probably already figured out, we can rotate through any constant angle by pre-calculating the cos(a) and sin(a) values then inserting them into the 2d rotation.
e.g.
sn = sin(30') = 0.5
cs = cos(30') = 0.86602540378...
x' = x * cs - y * sn
y' = x * sn + y * cs
using constants:
x' = x * 0.86602540378 - y * 0.5
y' = x * 0.5 + y * 0.86602540378
Division, are you crazy?
And now Ladies and Gentlemen what you have been waiting for, using division to replace the multiplications like on those 8-bit computers many moons ago.
Again, we can replace the sin(a) and cos(a) values with constants. This time we choose a 1 degree rotation.
sn = sin(1') = 0.01745240643
cs = cos(1') = 0.99984769515
x' = x * 0.99984769515 - y * 0.01745240643
y' = x * 0.01745240643 + y * 0.99984769515
x = x'
y = y'
We convert the sn and cs values into 1/sn and 1/cs values because we will be performing division instead of multiplication.
r_sn = 1/sin(1') = 57.2986884986
r_cs = 1/cos(1') = 1.00015232804
x' = x / r_cs - y / r_sn
y' = x / r_sn + y / r_cs
expanded:
x' = x / 1.00015232804 - y / 57.2986884986
y' = x / 57.2986884986 + y / 1.00015232804
And now the naughty bit. We round those numbers up or down to something more 'cpu-friendly'. ;)
a_sn = approx. 1/sin(1') = 57.2986884986 ---> 64
a_cs = approx. 1/cos(1') = 1.00015232804 ---> 1
x' = x / a_cs - y / a_sn
y' = x / a_sn + y / a_cs
expanded:
x' = x / 1 - y / 64
y' = x / 64 + y / 1
As you're probably already noticed, we can remove the divide-by-1 in each step to give this more pleasing method.
x' = x - y / 64
y' = x / 64 + y
Mr. Shifty:
x' = x - (y SHR 6)
y' = (x SHR 6) + y
Same:
x' = x - (y SHR 6)
y' = y + (x SHR 6)
In 80x86 using 1.15.16 fixed-point it looks like this...
(eax) = x SHL 65536
(edx) = y SHL 65536
mov ebx, eax ; old_x = x
mov ecx, edx ; old_y = y
sar ebx, 6 ; old_x / 64
sar ecx, 6 ; old_y / 64
sub eax, ecx ; x' = x - (old_y / 64)
add edx, ebx ; y' = y + (old_x / 64)
Go Timmy!!!
Now, there are a few problems with that division (shift) method. Firstly it will spiral outwards over a long period of time (remember we have messed with those important sin and cos values). Also if you do try smaller values for the shift-right counts (for example shr 4) then the amount of error is even worse. And of course you need to store and handle fixed-point or floating-point maths for it to work.
I doubt if this method will be used outside a size-optimization compo, but you never know. If you want to draw dodgy-looking spirals then see above. ;)
Have fun.